本文讨论的函数均为积性函数。
2.约数个数
方法一
网上大部分博客似乎都是这种方法,也很简单。
记 d[i] 为 i 的约数个数 , num[i] 为 i 的最小质因子的次数。
- i 为质数
此时 d[i]=2 , num[i]=1。
- prime[j] ∣ i
一个数的因数个数为:
i=1∏k(wi+1) (wi为指数)
prime[j] 加入只会影响第一项,即让 w1+1 变为 w1+2。
看一下定义,num[i] 就是 w1 , 所以此时 d[i∗prime[j]]=d[i]/(num[i]+1)∗(num[i]+2)
因为 prime[j] 是 i∗prime[j] 的最小质因子,所以 num[i∗prime[j]]=num[i]+1
- prime[j] ∣ i
由积性函数的性质得:d[i∗prime[j]]=d[i]∗d[prime[j]]
因为 prime[j] 是 i∗prime[j] 的最小质因子,所以 num[i∗prime[j]]=1
void sieve( ) {
d[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
d[ i ] = 2 , num[ i ] = 1;
}
for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) {
d[ i * prime[ j ] ] = d[ i ] / ( num[ i ] + 1 ) * ( num[ i ] + 2 );
num[ i * prime[ j ] ] = num[ i ] + 1;
break;
}
d[ i * prime[ j ] ] = d[ i ] * d[ prime[ j ] ];
num[ i * prime[ j ] ] = 1;
}
}
}
方法二.
上面的方法需要多开一个数组,太浪费空间了,介绍一种更简单的方法。
只讨论 prime[j] ∣ i 的情况,其余同上。
由约数个数公式得:
d[i]=j=1∏k(wj+1)=(w1+1)×j=2∏k(wj+1)
因为后面的根 prime[j](p1) 无关,为了方便记为 t。
又有:
d[i×p1]=(w1+1+1)×t=d[i]+t
d[i/p1]=(w1+1−1)×t=d[i]−t
两式相加得:
d[i×p1]+d[i/p1]=2×d[i]
移相得:
d[i×p1]=2×d[i]−d[i/p1]
即
d[i×prime[j]]=2×d[i]−d[i/prime[j]]
void sieve( ) {
d[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
d[ i ] = 2;
}
for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) {
d[ i * prime[ j ] ] = 2 * d[ i ] - d[ i / prime[ j ] ];
break;
}
d[ i * prime[ j ] ] = d[ i ] * d[ prime[ j ] ];
}
}
}
3.约数和
记 f[i] 为 i 的约数和。
- i 为质数
此时 f[i]=i+1。
- prime[j] ∣ i
由约数和公式有:
f[i]=d=1∏kj=0∑wdpdj=j=0∑w1p1j×d=2∏kj=0∑wdpdj=d=0∑w1p1d×t
其中 pd 为第 d 个质数 , wd 为第 d 个质数的指数。
prime[j] 的加入只会影响含 p1(最小质因子) 的式子,所以后面的根本不用考虑,为了方便记为 t。因为 prime[j] 就是 p1 , 下面简写。
考虑 f(i×p1) 与 f(i/p1)
f(i×p1)=d=0∑w1+1p1d×t=f(i)+p1w1+1×t (1)
f(i/p1)=d=0∑w1−1p1d×t=f(i)−p1w1×t
⇒p1×f(i/p1)=d=0∑w1−1p1d×t=p1×f(i)−p1w1+1×t (2)
(1)+(2) 得:
f(i×p1)+p1×f(i/p1)=(p1+1)×f(i)
f(i×p1)=(p1+1)×f(i)−p1×f(i/p1)
还原得:
f(i×prime[j])=(prime[j]+1)×f(i)−prime[j]×f(i/prime[j])
- prime[j] ∣ i
由积性函数的性质得:f[i∗prime[j]]=f[i]∗f[prime[j]]
void sieve( ) {
f[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
f[ i ] = i + 1;
}
for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) {
f[ i * prime[ j ] ] = ( prime[ j ] + 1 ) * f[ i ] - prime[ j ] * f[ i / prime[ j ] ];
break;
}
f[ i * prime[ j ] ] = f[ i ] * f[ prime[ j ] ];
}
}
}